#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

class Solution {
    public:
	int shortestPathAllKeys(vector<string> &grid)
	{
		int n = grid.size();
		int m = grid[0].size();
		vector<vector<vector<int>>> vis(n, vector<vector<int>>(m, vector<int>(1<<6, 0)));
		int omikeys = 0, startx = 0, starty = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (islower(grid[i][j])) {
					omikeys |= (1 << (grid[i][j] - 'a'));
				}
				if (grid[i][j] == '@') {
					startx = i;
					starty = j;
				}
			}
		}
		vector<int> direct = { -1, 0, 1, 0, -1 };
		queue<tuple<int, int, int, int>> q;
		q.emplace(startx, starty, 0, 0);
                vis[startx][starty][0] = 1;
		while (!q.empty()) {
			auto [x, y, keys, step] = q.front();
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + direct[i];
				int ny = y + direct[i + 1];
				int nkey = keys;
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == '#') {
					continue;
				}

				if (isupper(grid[nx][ny]) && (keys & (1 << (grid[nx][ny] - 'A'))) == 0) {
					continue;
				}

				if (islower(grid[nx][ny])) {
					nkey = keys | (1 << (grid[nx][ny] - 'a'));
				}

				if (nkey == omikeys) {
					return step + 1;
				}
				if (!vis[nx][ny][nkey]) {
					q.emplace(nx, ny, nkey, step + 1);
					vis[nx][ny][nkey] = 1;
				}
			}
		}
		return -1;
	}
};

int main()
{
	vector<string> grid = { "@.a..", "###.#", "b.A.B" };
	cout << Solution().shortestPathAllKeys(grid) << endl;
	return 0;
}